﻿using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace ns
{
    /// <summary>
    /// 堆栈队列类题目
    /// </summary>
    public class StackQueueQuestion : MonoBehaviour
    {





    }

    //232. 用栈实现队列 （波克城市面试题）
    //https://leetcode-cn.com/problems/implement-queue-using-stacks/
    //题解：https://leetcode-cn.com/problems/implement-queue-using-stacks/solution/yong-zhan-shi-xian-dui-lie-by-leetcode/
    //实现队列最直观的方法是用链表，但在这篇文章里我会介绍另一个方法 - 使用栈。
    //算法：2个栈入队 O（1），出队 摊还复杂度O（1）
    public class MyQueue
    {
        private Stack<int> s1;
        private Stack<int> s2;
        int front;        // 保存首个变量元素

        /** Initialize your data structure here. */
        public MyQueue()
        {
            s1 = new Stack<int>();
            s2 = new Stack<int>();
        }

        /** Push element x to the back of queue. */
        public void Push(int x)
        {
            s1.Push(x);  //将X入栈
        }

        /** Removes the element from in front of queue and returns that element. */
        public int Pop()
        {
            if (s2.Count == 0)
            {
                while (s1.Count != 0)
                {
                    s2.Push(s1.Pop()); //s2入栈，是s1出栈 ,时间复杂度为 O(2n) = O(n)
                }
            }
            return s2.Pop(); //摊还复杂度 O(1)O(1) 
        }

        /** Get the front element. */
        public int Peek()
        {
            if (s2.Count != 0)
            {
                return front = s2.Peek();
            }
            return front;
        }

        /** Returns whether the queue is empty. */
        public bool Empty()
        {
            return (s1.Count == 0 && s2.Count == 0); //判断s1和s2都存有队列的元素
        }
    }
    /**
     * Your MyQueue object will be instantiated and called as such:
     * MyQueue obj = new MyQueue();
     * obj.Push(x);
     * int param_2 = obj.Pop();
     * int param_3 = obj.Peek();
     * bool param_4 = obj.Empty();
     */

    //225. 用队列实现栈
    //https://leetcode-cn.com/problems/implement-stack-using-queues/
    //题解：https://leetcode-cn.com/problems/implement-stack-using-queues/solution/yong-dui-lie-shi-xian-zhan-by-leetcode-solution/z099qa-0000º0
    //算法：2个队列
    public class MyStack
    {
        Queue<int> q1;
        Queue<int> q2;


        /** Initialize your data structure here. */
        public MyStack()
        {
            q1 = new Queue<int>();
            q2 = new Queue<int>();
        }

        /** Push element x onto stack. */
        public void Push(int x)
        {
            q2.Enqueue(x);
            while (q1.Count!=0)
            {
                q2.Enqueue(q1.Dequeue());
            }
            Queue<int> temp = q1; //此时Q1位空，Q1和Q2对换,让Q2位空，Q1代表栈
            q1 = q2;
            q2 = temp;
        }

        /** Removes the element on top of the stack and returns that element. */
        public int Pop()
        {
            return q1.Dequeue();
        }

        /** Get the top element. */
        public int Top()
        {
            return q1.Peek();
        }

        /** Returns whether the stack is empty. */
        public bool Empty()
        {
            return (q1.Count == 0 && q2.Count == 0);
        }
    }

    //剑指 Offer 09. 用两个栈实现队列 LCOF
    //https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
    public class CQueue
    {
        private Stack<int> s1;
        private Stack<int> s2;

        public CQueue()
        {
            s1 = new Stack<int>();
            s2 = new Stack<int>();
        }

        //队尾添加整数
        public void AppendTail(int value)
        {
            s1.Push(value);
        }

        public int DeleteHead()
        {
            if (s2.Count == 0)
            {
                while (s1.Count != 0)
                {
                    s2.Push(s1.Pop());
                }
            }
            if (s2.Count == 0)
            {
                return -1;
            }
            else
            {
                int deleteItem = s2.Pop();
                return deleteItem;
            }

        }
    }
    /**
     * Your CQueue object will be instantiated and called as such:
     * CQueue obj = new CQueue();
     * obj.AppendTail(value);
     * int param_2 = obj.DeleteHead();
     */

   
}